#include "BTreeNode.h"

using namespace std;



BTLeafNode::BTLeafNode()
{
	NodePtr = (leafNode*)buffer;
	NodePtr->nextNode = -1;
	NodePtr->keyCount = 0;
	NodePtr->empty = 0;
}


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc = pf.read(pid, buffer);
	return rc;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	return NodePtr->keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	tuple temp;
	temp.rd = rid;
	temp.key = key;
	int count = NodePtr->keyCount;
	if(count >= MaxNumOfTuples)
	{
		return RC_NODE_FULL;
	}
	int eid;
	if(locate(key, eid) == 0)
	{
		for(int k = count; k > eid; k--)
		{
			NodePtr->tuples[k] = NodePtr->tuples[k-1];
		}
		NodePtr->tuples[eid] = temp;
		NodePtr->keyCount += 1;
	}
	else
	{
		NodePtr->tuples[count] = temp;
		NodePtr->keyCount += 1;
	}
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	tuple temp;
	temp.rd = rid;
	temp.key = key;
	int eid;
	tuple array[MaxNumOfTuples+1];
	if(locate(key, eid) == 0)
	{
		int k = 0;
		for(; k < eid; k++)
		{
			array[k] = NodePtr->tuples[k];
		}
		array[eid] = temp;
		for(; k < MaxNumOfTuples; k++)
		{
			array[k+1] = NodePtr->tuples[k];
		}
	}
	else
	{
		for(int k = 0; k < MaxNumOfTuples; k++)
		{
			array[k] = NodePtr->tuples[k];
		}
		array[MaxNumOfTuples+1] = temp;
	}
	int half = (MaxNumOfTuples+1)/2;
	for(int k = 0; k < half; k++)
	{
		NodePtr->tuples[k] = array[k];
	}
	NodePtr->keyCount = half;
	for(int k = half; k < MaxNumOfTuples+1; k++)
	{
		sibling.insert(array[k].key, array[k].rd);
	}
	siblingKey = array[half].key;
	return 0;
	
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)		//!!!!!!!!!!!!!!! here, eid starts from 0
{ 
	int count = NodePtr->keyCount;
	int k;
	for(k = 0; k < count; k++)
	{
		if(NodePtr->tuples[k].key >= searchKey)
		{
			break;
		}
	}
	if(k == count)
	{
		return RC_NO_SUCH_RECORD;
	}
	else
	{
		eid = k;
		return 0;
	}
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	if(eid >= NodePtr->keyCount)
		return RC_NO_SUCH_RECORD;
	key = NodePtr->tuples[eid].key;
	rid = NodePtr->tuples[eid].rd;
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 

	return NodePtr->nextNode;

}




/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	NodePtr->nextNode = pid;
	return 0;
}


BTNonLeafNode::BTNonLeafNode()
{
	NodePtr = (nonLeafNode*)buffer;
	NodePtr->keyCount = 0;
	NodePtr->leftMost = -1;

}	




/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	RC rc = pf.read(pid, buffer);
	return rc;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	return NodePtr->keyCount;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	mate temp;
	temp.pd = pid;
	temp.key = key;
	int count = NodePtr->keyCount;
	if(count >= MaxNumOfMates)
	{
		return RC_NODE_FULL;
	}
	int eid = 0;
	for(; eid < count; eid++)
	{
		if(NodePtr->mates[eid].key >= key)
		{
			break;
		}
	}
	
	for(int k = count; k > eid; k--)
	{
		NodePtr->mates[k] = NodePtr->mates[k-1];
	}
	
	NodePtr->mates[eid] = temp;
	NodePtr->keyCount += 1;
	

	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	mate temp;
	temp.pd = pid;
	temp.key = key;
	int eid = 0;
	mate array[MaxNumOfMates+1];
	
	for(; eid < MaxNumOfMates; eid++)
	{
		if(NodePtr->mates[eid].key >= key)
		{
			break;
		}
	}

	int i = 0;
	for(; i < eid; i++)
	{
		array[i] = NodePtr->mates[i];
	}
	array[eid] = temp;
	for(; i < MaxNumOfMates; i++)
	{
		array[i+1] = NodePtr->mates[i];
	}


	int half = (MaxNumOfMates+1)/2;
	
	for(int k = 0; k < half; k++)
	{
		NodePtr->mates[k] = array[k];
	}
	NodePtr->keyCount = half;
	
	midKey = array[half].key;
	
	sibling.setLeftPtr(array[half].key);
	
	for(int k = half+1; k < MaxNumOfMates+1; k++)
	{
		sibling.insert(array[k].key, array[k].pd);
	}

	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int count = NodePtr->keyCount;
	if(count == 0)
	{
		pid = NodePtr->leftMost;
		return 0;
	}
	int k;
	for(k = 0; k < count; k++)
	{
		if(NodePtr->mates[k].key > searchKey)
		{
			break;
		}
	}
	if(k == count)
	{
		pid = NodePtr->mates[count-1].pd;
	}
	else
	{
		if(k == 0)
		{
			pid = NodePtr->leftMost;
		}
		else
		{
			pid = NodePtr->mates[k-1].pd;
		}
	}
	
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	NodePtr->leftMost = pid1;
	mate temp;
	temp.key = key;
	temp.pd = pid2;
	NodePtr->mates[0] = temp;
	NodePtr->keyCount = 1;
	
	return 0;
	
}


RC BTNonLeafNode::setLeftPtr(PageId left)
{
	NodePtr->leftMost = left;
}

//just for testing
RC BTNonLeafNode::readEntry(int eid, int& key, PageId& rid)
{
	if(eid >= NodePtr->keyCount)
		return RC_NO_SUCH_RECORD;
	key = NodePtr->mates[eid].key;
	rid = NodePtr->mates[eid].pd;
	return 0;
}

